/**
 * 
 */
package array.passed;

/**
 * @author xyyi
 *
 */
public class SetMatrixZeroes {

	/**
	Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
	Follow up:

	Did you use extra space?
	A straight forward solution using O(mn) space is probably a bad idea.
	A simple improvement uses O(m + n) space, but still not the best solution.
	Could you devise a constant space solution?	
	*/
	public void setZeroes(int[][] matrix) {
		if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
			return;
		int rows = matrix.length, cols = matrix[0].length;
		boolean isFirstRow0 = false, isFirstCol0 = false;
		for (int i = 0; i < rows; i++) {
			if (matrix[i][0] == 0) {
				isFirstCol0 = true;
				break;
			}
		}

		for (int i = 0; i < cols; i++) {
			if (matrix[0][i] == 0) {
				isFirstRow0 = true;
				break;
			}
		}

		// check all matri1
		for (int row = 1; row < rows; row++) {
			for (int col = 1; col < cols; col++) {
				if (matrix[row][col] == 0) {
					matrix[row][0] = 0;
					matrix[0][col] = 0;
				}
			}
		}

		for (int row = 1; row < rows; row++) {
			if (matrix[row][0] == 0) {
				for (int col = 0; col < cols; col++) {
					matrix[row][col] = 0;
				}
			}
		}

		for (int col = 1; col < cols; col++) {
			if (matrix[0][col] == 0) {
				for (int row = 0; row < rows; row++) {
					matrix[row][col] = 0;
				}
			}
		}

		if (isFirstCol0) {
			for (int row = 0; row < rows; row++) {
				matrix[row][0] = 0;
			}
		}

		if (isFirstRow0) {
			for (int col = 0; col < cols; col++) {
				matrix[0][col] = 0;
			}
		}
	}

	/**
	 * 
	 */
	public SetMatrixZeroes() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		SetMatrixZeroes smz = new SetMatrixZeroes();
		int[][] matrix = { { 1, 0, 3 } };
		smz.setZeroes(matrix);

	}

}
